package com.booby.algorithm.quick;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 单轴快排，从小到大。
 *
 * 思路：左右两个指针，左指针向右，右指针向左，当发现左边指针所指的数比右边大。则进行交换。
 *
 * @author: lizt
 * @date: 2020/8/24 08:55
 **/

public class MinToMax {
//    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};
    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};
//    public static final Integer[] arr = {1,3,8,7,4,5};

    public static void sorted(Integer[] arr, int leftBound, int rightBound){
        if (leftBound >= rightBound){
            return;
        }
        int mid = partition(arr, leftBound, rightBound);
//        Utils.print(arr);
        sorted(arr, leftBound, mid - 1);
        sorted(arr, mid + 1, rightBound);
    }
// [1,3,8,7,4,5]  [1,3,4,7,8,5]
    public static int partition(Integer[] arr, int leftBound, int rightBound){
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound -1;
        // =决定首元素是否交换
        while (left <= right){
            // left <= right  = 决定轴的交换
            // arr[left] <= pivot 决定如果集合元素和轴的值相等，则跳过不处理
            while (left <= right && arr[left] <= pivot){
                left++;
            }
            while (left <= right && arr[right] > pivot){
                right--;
            }
            if (left < right){
                Utils.swap(arr, left, right);
            }
        }
        // 交换轴
        Utils.swap(arr, left, rightBound);
        return left;
    }

    public static void main(String[] args) {
        sorted(arr, 0, arr.length-1);
        Utils.print(arr);
    }
}
